/**
 * Created by zhourh on 2018/7/31.
 *
 * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

 如果有两个中间结点，则返回第二个中间结点。

 */
public class MiddleOfTheLinkedList {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.println(new MiddleOfTheLinkedList().middleNode(head));
        head.next.next.next.next.next = new ListNode(6);
        System.out.println(new MiddleOfTheLinkedList().middleNode(head));
    }

    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        //先获得总节点数
        int nodeCount = 0;
        ListNode node = head;
        while (node != null) {
            nodeCount++;
            node = node.next;
        }

        int mid = nodeCount / 2;
        ListNode ans = head;
        while (mid > 0) {
            ans = ans.next;
            mid--;
        }

        return ans;
    }
}
